/*
 * @lc app=leetcode.cn id=19 lang=cpp
 *
 * [19] 删除链表的倒数第 N 个结点
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start

// Definition for singly-linked list.
//  struct ListNode {
//      int val;
//      LisNode *next;
//      ListNode() : val(0), next(nullptr) {}
//      ListNode(int x) : val(x), next(nullptr) {}
//      ListNode(int x, ListNode *next) : val(x), next(next) {}
// };

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //双指针
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        //第二个指针指向head前一个元素，所以至少是可以删的
        ListNode* second = dummy;
        //前后指针相差n个
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        //然后前后指针同时向后，直到第一个指针为空
        //因为两个指针相差n，所以第二个指针指向的就是倒数第n个元素
        while (first) {
            first = first->next;
            second = second->next;
        }
        //只有一个节点的话second就等于nullptr
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};
// @lc code=end

// 先求长度后遍历法，两趟扫描了
// int length = 0;
//     auto node = head;
//     while(node) {
//         length++;
//         node = node->next;
//     }
//     int m = length - n;
//     if(m == 0) {
//         if(head->next) {
//             return head->next;
//         }else {
//             head = nullptr;
//             return head;
//         }
//     }
//     node = head;
//     for(int i = 0;i < m-1;i++) {
//         node = node->next;
//     }
//     if(node->next->next) {
//         node->next = node->next->next;
//     }else {
//         node->next = nullptr;  
//     }
//     return head;

